package com.github.hgkmail.hello.leetcode101.dp.divideconquer;

public class LC169MajorityElement {
    //Boyer-Moore 摩尔投票法
    public int majorityElement(int[] nums) {
        if (nums.length<=0) {
            return -1;
        }
        int curr=-1, times=0;
        //进行投票
        for (int i = 0; i < nums.length; i++) {
            if (curr==nums[i]) {
                times++;
                continue;
            }
            if (times>0) {
                times--;
            } else {
                curr=nums[i];
                times=1;
            }
        }
        return curr;
    }

    //分治思想：分成2个数组，众数一定是其中一个子数组的众数，对于2个众数a1、a2，分别统计次数(countInRange)来决出胜负。
    public int majorityElement2(int[] nums) {
        //todo
        return 0;
    }

    public static void main(String[] args) {

    }
}
